package SortAlgorithm;

import com.alibaba.fastjson.JSON;

import java.util.Random;

public class 快速排序 implements ISort {

    /**
     * 最坏的情况: 选择的基数是当前区域内最大或者最小的数,
     * 那么就会造成 左区域 满 ,右区域 0,会一直 n n-1 n-2 n-3...这样最坏的情况排序下去
     * 最坏时间复杂度: n^2;空间复杂度 O(logn)因为递归调用空间,平均调用logn次
     */
    private Random random = new Random();

    @Override
    public int[] sort(int[] arr) {
        return this.fastSort(arr);
    }

    private int[] fastSort(int[] arr) {
        this.split(arr, 0, arr.length - 1);
        return arr;
    }

    // 得到中点,然后递归切割
    private void split(int[] arr, int left, int right) {

        if (left >= right) {
            return;
        }

        // 随机取一位放在首位
        int index = this.random.nextInt((right - left) + 1) + left;
        this.swap(arr, left, index);

        int mid = this.partSort(arr, left, right);
        this.split(arr, left, mid);
        this.split(arr, mid + 1, right);

    }

    // 局部排序
    private int partSort(int[] arr, int left, int right) {

        while (left < right) {

            // 从右边找一个比当前小的
            while (left < right && arr[left] <= arr[right]) {
                right--;
            }
            this.swap(arr, left, right);

            // 从左边找一个比当前大的
            while (left < right && arr[left] <= arr[right]) {
                left++;
            }
            this.swap(arr, left, right);

        }

        return left;
    }

    private void swap(int[] arr, int index1, int index2) {
        int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }

    public static void main(String[] args) {
        快速排序 n = new 快速排序();
        int[] arr = {5, 4, 3, 1, 2, 19, 53, 135, 64, 3};
        int[] result = n.fastSort(arr);
        System.out.println(JSON.toJSONString(result));
    }

}
